package Demo49;

/**
 * 交易逆序对的总数
 * https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/submissions/539293318/
 */
class Solution {
    int[] ns;
    public int reversePairs(int[] nums) {
        ns = new int[nums.length];
        int ret = margetSort(nums, 0, nums.length - 1);
        return ret;
    }
    // 降序
    private int margetSort(int[] nums, int begin, int end) {
            if(begin >= end) {
                return 0;
            }
            int mid = (begin + end) / 2;
            int ret = 0;
            ret += margetSort(nums, begin, mid);
            ret += margetSort(nums, mid + 1, end);

            int i = 0, left = begin, right = mid + 1;
            while(left <= mid && right <= end) {
                if(nums[left] > nums[right]) {
                    ret += (end - right) + 1;
                    ns[i++] = nums[left++];
                }else {
                    // nums[left] <= nums[right]
                    ns[i++] = nums[right++];
                }
            }

            // 处理边界值
            while(left <= mid) {
                ns[i++] = nums[left++];
            }
            // 处理边界值
            while(right <= end) {
                ns[i++] = nums[right++];
            }
            // 归并
            for(int j = begin; j <= end; j++) {
                nums[j] = ns[j - begin];
            }
            return ret;
        }
    // 升序
//    private int margetSort(int[] nums, int begin, int end) {
//        if(begin >= end) {
//            return 0;
//        }
//        int mid = (begin + end) / 2;
//        int ret = 0;
//        ret += margetSort(nums, begin, mid);
//        ret += margetSort(nums, mid + 1, end);
//
//        int i = 0, left = begin, right = mid + 1;
//        while(left <= mid && right <= end) {
//            if(nums[left] <= nums[right]) {
//                ns[i++] = nums[left++];
//            }else {
//                // nums[left] > nums[right]
//                ret += (mid - left) + 1;
//                ns[i++] = nums[right++];
//
//            }
//        }
//
//        // 处理边界值
//        while(left <= mid) {
//            ns[i++] = nums[left++];
//        }
//        // 处理边界值
//        while(right <= end) {
//            ns[i++] = nums[right++];
//        }
//        // 归并
//        for(int j = begin; j <= end; j++) {
//            nums[j] = ns[j - begin];
//        }
//        return ret;
//    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.reversePairs(new int[] {9,7,5,4,6});
        System.out.println("ret: " + ret);
    }
}